package leetcode_1001_1100;

import java.util.*;

public class LeeCode_1054 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(rearrangeBarcodes(new int[]{1, 1, 1, 2, 2, 2})));
        System.out.println(Arrays.toString(rearrangeBarcodes(new int[]{2,2,2,1,5})));
    }
    private static int[] rearrangeBarcodes(int[] barcodes) {
        Arrays.sort(barcodes);
        int n = barcodes.length;
        PriorityQueue<int[]> list = new PriorityQueue<>((o1, o2) -> {
            int c1 = o1[1] - o1[0] + 1;
            int c2 = o2[1] - o2[0] + 1;
            return c2 - c1;
        });
        int i = 1, pre = barcodes[0], start = 0;
        while (i < n){
            if (barcodes[i] != pre){
                list.add(new int[]{start, i - 1});
                pre = barcodes[i];
                start = i;
            }
            i++;
        }
        list.add(new int[]{start, n - 1});
        int[] ans = new int[n];
        int[] poll = list.poll();
        ans[0] = barcodes[poll[0]];
        poll[0]++;
        if (poll[0] <= poll[1]){
            list.add(poll);
        }
        i = 1;
        while (i < n){
            int[] poll1 = list.poll();
            if (barcodes[poll1[0]] != ans[i - 1]){
                ans[i] = barcodes[poll1[0]];
                poll1[0]++;
                if (poll1[0] <= poll1[1]){
                    list.add(poll1);
                }
            }else {
                int[] poll2 = list.poll();
                list.add(poll1);
                ans[i] = barcodes[poll2[0]];
                poll2[0]++;
                if (poll2[0] <= poll2[1]){
                    list.add(poll2);
                }
            }
            i++;
        }
        return ans;
    }
}
